package 算法;

import java.util.Stack;

//https://leetcode-cn.com/problems/route-between-nodes-lcci/
public class 节点间的通路 {
    public static void main(String[] args) {
        int[] i = new int[]{1,2,3};

    }
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        //这里用栈解决+数组解决（数组中存放已经用的根节点）
        int[] res = new int[n]; //有了就是1
        res[start] = 1;

        Stack<Integer> stack = new Stack<>();
        for (int[] ints : graph) {
            if(ints[0] == start){
                if(ints[1] == target) return true;
                stack.push(ints[1]);
            }
        }
        int i =0;
        while (!stack.isEmpty()){
            i = stack.pop();
                //表示以i为根节点还没用过
                for (int[] ints : graph) {
                    if(ints[0] == i){
                        if(ints[1] == target) return true;
                        if(res[ints[1]] == 0)
                            stack.push(ints[1]);
                    }

            }
        }
        return false;
    }

}
